package bstdynamicset;

import readfile.ReadStringFile;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import project1driver.SetData;

public class BSTDynamicSet<E, K extends Comparable<K>> 
{
	/**
	 * Private class for a BSTNode
	 * @author Ryne
	 *
	 * @param <E>
	 * @param <K>
	 */
	private static class BSTNode<E, K extends Comparable<K>> implements Comparable<BSTNode<E, K>> 
	{
		private E data;
		private K key;
		private BSTNode<E, K> parent;
		private BSTNode<E, K> leftChild;
		private BSTNode<E, K> rightChild;
		
		private BSTNode()
		{
			data = null;
			key = null;
			parent = null;
			leftChild = null;
			rightChild = null;
		}
		
		private BSTNode(E data, K key)
		{
			this.data = data;
			this.key = key;
			parent = null;
			leftChild = null;
			rightChild =null;
		}
		
		private BSTNode(E data, K key, BSTNode<E, K> left, BSTNode<E, K> right)
		{
			this.data = data;
			this.key = key;
			parent = null;
			leftChild = left;
			rightChild = right;
		}
		
		public int compareTo(BSTNode<E, K> node)
		{
			return this.key.compareTo(node.key);
		}
		
		public String toString()
		{
			return key.toString();
		}
	}
	
	
	// ****** Class data ******
	private BSTNode<E, K> root;
	private int size;
	
	private static long startTime;
	private static long duration;
	private static long minTime;
	private static long maxTime;
	private static long aveTime;
	private static long time_sum;
	private SetData bst_data;
	private ArrayList<BSTNode<E, K>> bst_elements;
	
	public BSTDynamicSet()
	{
		root = null;
		size = 0;
		bst_data = new SetData("BST");
		bst_elements = new ArrayList<BSTNode<E, K>>(0);
	}
	
	public BSTDynamicSet(BSTNode<E, K> node)
	{
		root = node;
		size = 0;
		bst_data = new SetData("BST");
		bst_elements = new ArrayList<BSTNode<E, K>>(0);
	}
	
	// ****** Class methods ******
	
	public void resetTime()
	{
		startTime = 0;
		duration = 0;
		minTime = 0;
		maxTime = 0;
		aveTime = 0;
		time_sum = 0;
	}
	
	public SetData runtest(Object[] fileData, int[] randomIndices)
	{
		resetTime();
		
		// Insert data
		for(int i = 0; i < fileData.length; i++)
		{
			startTime = System.nanoTime();
			this.insertData((E) fileData[i], (K) fileData[i]);
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		bst_data.insert_results[0] = minTime;
		bst_data.insert_results[1] = aveTime;
		bst_data.insert_results[2] = maxTime;
		
		// Search data
		resetTime();
		
		for(int i = 0; i < 10; i++)
		{
			startTime = System.nanoTime();
			bst_elements.add(search((K) fileData[randomIndices[i]]));
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		bst_data.search_results[0] = minTime;
		bst_data.search_results[1] = aveTime;
		bst_data.search_results[2] = maxTime;
		
		// Predecessor data
		resetTime();
		
		for(int i = 0; i < 10; i++)
		{
			startTime = System.nanoTime();
			predecessor(bst_elements.get(i));
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		bst_data.pred_results[0] = minTime;
		bst_data.pred_results[1] = aveTime;
		bst_data.pred_results[2] = maxTime;
		
		// Successor data
		resetTime();
		
		for(int i = 0; i < 10; i++)
		{
			startTime = System.nanoTime();
			successor(bst_elements.get(i));
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		bst_data.succ_results[0] = minTime;
		bst_data.succ_results[1] = aveTime;
		bst_data.succ_results[2] = maxTime;
		
		// Maximum data
		resetTime();
		startTime = System.nanoTime();
		maximum();
		duration = System.nanoTime() - startTime;
		
		bst_data.timeOfMax = duration;
		
		// Minimum data
		resetTime();
		startTime = System.nanoTime();
		minimum();
		duration = System.nanoTime() - startTime;
		
		bst_data.timeOfMin = duration;
		
		
		return bst_data;
	}
	
	/**
	 * insertData
	 * 
	 * Description: public wrapper method to insert a node with a
	 * given data and key
	 * 
	 * @param nodeData
	 * @param nodeKey
	 */
	public void insertData(E nodeData, K nodeKey)
	{
		insert(new BSTNode<E, K>(nodeData, nodeKey));
	}
	
	/**
	 * insert
	 * 
	 * Description: method to insert a node into the tree
	 * 
	 * @param nodeToAdd
	 */
	public void insert(BSTNode<E, K> nodeToAdd)
	{
		iterativeInsert(nodeToAdd);
		size++;
	}
	
	/**
	 * iterativeInsert
	 * 
	 * Description: private method to iteratively insert a node
	 * 
	 * @param nodeToInsert
	 */
	private void iterativeInsert(BSTNode<E, K> nodeToInsert)
	{
		BSTNode<E, K> trailingNode = null;
		BSTNode<E, K> previousNode = root;
		
		while(previousNode != null)
		{
			trailingNode = previousNode;
			if(nodeToInsert.key.compareTo(previousNode.key) < 0)
			{
				previousNode = previousNode.leftChild;
			}
			else
			{
				previousNode = previousNode.rightChild;
			}
		}
		
		nodeToInsert.parent = trailingNode;
		if(trailingNode == null)
		{
			root = nodeToInsert;
		}
		else if(nodeToInsert.key.compareTo(trailingNode.key) < 0)
		{
			trailingNode.leftChild = nodeToInsert;
		}
		else
		{
			trailingNode.rightChild = nodeToInsert;
		}
	}
	
	/*
	private BSTNode<E, K> recursiveInsert(BSTNode<E, K> localRoot, BSTNode<E, K> nodeToAdd)
	{
		if(localRoot == null)
		{
			return nodeToAdd;
		}
		else
		{
			if(nodeToAdd.key.compareTo(localRoot.key) < 0)
			{
				localRoot.leftChild = recursiveInsert(localRoot.leftChild, nodeToAdd);
			}
			else if(nodeToAdd.key.compareTo(localRoot.key) > 0)
			{
				localRoot.rightChild = recursiveInsert(localRoot.rightChild, nodeToAdd);
			}
			
			return localRoot;
		}
	}
	*/
	
	public boolean deleteKey(K searchKey)
	{
		BSTNode<E, K> result = search(searchKey);
		boolean keyDeleted = false;
		
		if(result != null)
		{
			delete(result);
			keyDeleted = true;
		}
		
		return keyDeleted;
	}
	
	/**
	 * delete
	 * 
	 * Description: given a pointer to a node that exists in the tree
	 * this method deletes the node
	 * 
	 * @param nodeToDelete
	 */
	public void delete(BSTNode<E, K> nodeToDelete)
	{
		if(nodeToDelete.leftChild == null)
		{
			transplant(nodeToDelete, nodeToDelete.rightChild);
		}
		else if(nodeToDelete.rightChild == null)
		{
			transplant(nodeToDelete, nodeToDelete.leftChild);
		}
		else
		{
			BSTNode<E, K> minOfRight = minimumOfNode(nodeToDelete.rightChild);
			
			if(minOfRight.parent != nodeToDelete)
			{
				transplant(minOfRight, minOfRight.rightChild);
				minOfRight.rightChild = nodeToDelete.rightChild;
				minOfRight.rightChild.parent = minOfRight;
			}
			
			transplant(nodeToDelete, minOfRight);
			
			minOfRight.leftChild = nodeToDelete.leftChild;
			minOfRight.leftChild.parent = minOfRight;
		}
		
		size--;
	}
	
	/**
	 * transplant
	 * 
	 * Description: private method to assist in node deletion
	 * @param firstNode
	 * @param secondNode
	 */
	private void transplant(BSTNode<E, K> firstNode, BSTNode<E, K> secondNode)
	{
		if(firstNode.parent == null)
		{
			root = secondNode;
		}
		else if(firstNode == firstNode.parent.leftChild)
		{
			firstNode.parent.leftChild = secondNode;
		}
		else
		{
			firstNode.parent.rightChild = secondNode;
		}
		
		if(secondNode != null)
		{
			secondNode.parent = firstNode.parent;
		}
	}
	
	/*
	private BSTNode<E, K> remove(BSTNode<E, K> node)
	{
		if(node.leftChild == null)
		{
			// Replace with rightChild
			node = node.rightChild;
		}
		else if(node.rightChild == null)
		{
			// Replace with leftChild
			node = node.leftChild;
		}
		else
		{
			node = rightMostNode(node.leftChild);
			node.leftChild = remove(node.leftChild);
		}
		
		return node;
	}
	*/
	
	/**
	 * size
	 * 
	 * Description: returns the size of the tree (number of nodes)
	 * @return
	 */
	public int size()
	{
		return size;
	}
	
	/**
	 * searchForKey
	 * 
	 * Description: public wrapper method to search the tree for 
	 * a key and returns a pointer if it exists
	 * 
	 * @param key
	 * @return
	 */
	public K searchForKey(K searchKey)
	{
		BSTNode<E, K> result = search(searchKey);
		
		if(result != null)
		{
			return result.key;
		}
		else
		{
			return null;
		}
	}
	
	/**
	 * search
	 * 
	 * Description: private method to search the tree for a key
	 * @param searchKey
	 * @return
	 */
	private BSTNode<E, K> search(K searchKey)
	{
		BSTNode<E, K> localRoot = root;
		
		while(localRoot != null && localRoot.key.compareTo(searchKey) != 0)
		{
			if(searchKey.compareTo(localRoot.key) < 0)
			{
				localRoot = localRoot.leftChild;
			}
			else
			{
				localRoot = localRoot.rightChild;
			}
		}
		
		return localRoot;
	}
	
	/*
	private BSTNode<E, K> recursiveSearch(BSTNode<E, K> localroot, K key)
	{
		if(localroot == null)
		{
			return null;
		}
		
		if(localroot.key.compareTo(key) == 0)
		{
			return localroot;
		}
		else
		{
			if(key.compareTo(localroot.key) < 0)
			{
				return recursiveSearch(localroot.leftChild, key);
			}
			else if(key.compareTo(localroot.key) > 0)
			{
				return recursiveSearch(localroot.rightChild, key);
			}
			else
			{
				return null;
			}
		}
	}
	
	*/
	
	/**
	 * minimum
	 * 
	 * Description: returns the minimum node in the tree
	 * @return
	 */
	public BSTNode<E, K> minimum()
	{
		return minimumOfNode(root);
	}
	
	/**
	 * minimumOfNode
	 * 
	 * Description: returns the minimum of a given subtree
	 * at node
	 * 
	 * @param node
	 * @return
	 */
	private BSTNode<E, K> minimumOfNode(BSTNode<E, K> node)
	{
		while(node.leftChild != null)
		{
			node = node.leftChild;
		}
		return node;
	}
	
	/*
	private BSTNode<E, K> leftMostNode(BSTNode<E, K> localroot)
	{
		if(localroot != null)
		{
			if(localroot.leftChild == null)
			{
				return localroot;
			}
			else
			{
				return leftMostNode(localroot.leftChild);
			}
		}
		else
		{
			return null;
		}
	}
	*/
	
	/**
	 * maximum
	 * 
	 * Description: Returns the maximum node in the tree
	 * @return
	 */
	public BSTNode<E, K> maximum()
	{
		return maximumOfNode(root);
	}
	
	/**
	 * maximumOfNode
	 * Description: Returns the rightmost node of the subtree
	 * with the root at node
	 * 
	 * @param node
	 * @return
	 */
	private BSTNode<E, K> maximumOfNode(BSTNode<E, K> node)
	{
		while(node.rightChild != null)
		{
			node = node.rightChild;
		}
		return node;
	}
	
	/*
	private BSTNode<E, K> rightMostNode(BSTNode<E, K> localroot)
	{
		if(localroot != null)
		{
			if(localroot.rightChild == null)
			{
				return localroot;
			}
			else
			{
				return rightMostNode(localroot.rightChild);
			}
		}
		else
		{
			return null;
		}
	}
	*/
	
	/**
	 * findSuccessor
	 * 
	 * Description: public wrapper method to search for the successor of a key
	 * 
	 * @param searchKey
	 * @return
	 */
	
	public K findSuccessor(K searchKey)
	{
		BSTNode<E, K> result = search(searchKey);
		
		if(result != null)
		{
			result = successor(result);
		}
		
		if(result != null)
		{
			return result.key;
		}
		return null;
	}
	
	/**
	 * successor
	 * 
	 * Description: Returns the node after node
	 * @param node
	 * @return
	 */
	public BSTNode<E, K> successor(BSTNode<E, K> node)
	{
		BSTNode<E, K> parentNode;
		
		if(node.rightChild != null)
		{
			return minimumOfNode(node.rightChild);
		}
		
		parentNode = node.parent;
		
		while(parentNode != null && node == parentNode.rightChild)
		{
			node = parentNode;
			parentNode = parentNode.parent;
		}
		
		return parentNode;
	}
	
	/**
	 * findPredecessor
	 * 
	 * Description: public wrapper method to search for a predecessor
	 * 
	 * @param searchKey
	 * @return
	 */
	public K findPredecessor(K searchKey)
	{
		BSTNode<E, K> result = search(searchKey);
		
		if(result != null)
		{
			result = predecessor(result);
		}
		
		if(result != null)
		{
			return result.key;
		}
		return null;
	}
	
	/**
	 * predecessor
	 * 
	 * Description: Returns the node before node
	 * @param node
	 * @return
	 */
	public BSTNode<E, K> predecessor(BSTNode<E, K> node)
	{
		BSTNode<E, K> parentNode;
		
		if(node.leftChild != null)
		{
			return maximumOfNode(node.leftChild);
		}
		
		parentNode = node.parent;
		
		while(parentNode != null && node == parentNode.leftChild)
		{
			node = parentNode;
			parentNode = parentNode.parent;
		}
		
		return parentNode;
	}
	
	/**
	 * toString
	 * 
	 * Description: returns a string representation of the tree
	 * @Override
	 */
	public String toString()
	{
		String printedString = "";
		
		printedString = inorderPrint(root, printedString);
		
		return printedString;
	}
	
	/**
	 * inorderPrint
	 * 
	 * Description: private recursive method to generate a string representation
	 * of the tree
	 * 
	 * @param localroot
	 * @param dataToPrint
	 * @return
	 */
	private String inorderPrint(BSTNode<E, K> localroot, String dataToPrint)
	{
		if(localroot != null)
		{
			dataToPrint = inorderPrint(localroot.leftChild, dataToPrint);
			if(dataToPrint == "")
			{
				dataToPrint = localroot.toString() + "\n";
			}
			else
			{
				dataToPrint = dataToPrint.concat(localroot.toString() + "\n");
			}
			//System.out.println(localroot.key, dataToPrint);
			dataToPrint = inorderPrint(localroot.rightChild, dataToPrint);
			
		}
		
		return dataToPrint;
	}
	
	/**
	 * Unit tester
	 * 
	 * @param args
	 */
	public static void main(String[] args)
	{
		char command = '0';
		Scanner readInput = new Scanner(System.in);
		String key = null;
		String data = null;
		BSTNode<String, String> searchResult = null;
		String keyAndData;
		
		BSTDynamicSet<String, String> testList = new BSTDynamicSet<String, String>();
		
		readInput.useDelimiter("\n");
		
		System.out.println("Unit test for BSTDynamicSet and BSTNode\n");
		
		while(command != 'q')
		{
			System.out.print(
					"\n\n\n******   Command Menu   ******\n\n" +
					"1) Insert item\n" +
					"2) Delete item\n" +
					"3) Get size of list\n" +
					"4) Get minimum\n" +
					"5) Get maximum\n" +
					"6) Find successor\n" +
					"7) Find predecessor\n" +
					"8) Print keys\n" +
					"9) Read data from file\n" +
					"q) Quit\n\n" +
					": "
					);
			command = readInput.next().toCharArray()[0];
			
			switch(command)
			{
			case '1':
				data = null;
				key = null;
				
				System.out.print("\n\n******   Test insert   ******" + "\n" +
						"Enter node data: "
						);
				data = readInput.next();
				
				System.out.print("Enter node key: ");
				key = readInput.next();
				
				testList.insert(new BSTNode<String, String>(data, key, null, null));
				
				break;
			case '2':
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Test delete   ******" + "\n" +
						"Enter key: "
						);
				key = readInput.next();
				
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					testList.delete(searchResult);
					System.out.println("Key deleted.");
				}
				else
				{
					System.out.println("Key not found.");
				}
				
				break;
			case '3':
				System.out.print("\n\n******   Size of list ******\n" +
						"Number of elements: " + testList.size()
						);
				break;
			case '4':
				System.out.print("\n\n******   Get minimum   ******\n" +
						"Minimum key: " + testList.minimum()
						);
				break;
			case '5':
				System.out.print("\n\n******   Get maximum   ******\n" +
						"Maximum key: " + testList.maximum()
						);
				break;
			case '6':
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Find successor   ******\n" +
						"Enter key: "
						);
				
				key = readInput.next();
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					System.out.println("Successor: " + testList.successor(searchResult));
				}
				else
				{
					System.out.println("Key not found");
				}
				
				break;
			case '7': 
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Find predecessor   ******\n" +
						"Enter key: "
						);
				key = readInput.next();
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					System.out.println("Predecessor: " + testList.predecessor(searchResult));
				}
				else
				{
					System.out.println("Key not found");
				}
				break;
			case '8':
				System.out.println(testList);
				break;
			case '9':
				System.out.print("\n\n******   Read data from file   ******" + "\n" +
						"Enter a file name: "
						);
				ReadStringFile fileToRead = new ReadStringFile(readInput.next());
				try {
					while(fileToRead.hasLine())
					{
						keyAndData = fileToRead.readLine();
						testList.insert(new BSTNode<String, String>(keyAndData, keyAndData));
					}
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				break;
			case 'q':
				System.out.println("Exiting program...");
				break;
			default:
				System.out.println("Please choose a valid option.");
			}
			
		}
	}
}
